Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands

摘要

We study a random sampling technique to approximate integrals$\int_{[0,1]^s}f(\mathbf{x})\,\mathrm{d}\mathbf{x}$ by averaging the functionat some sampling points. We focus on cases where the integrand is smooth, whichis a problem which occurs in statistics. The convergence rate of theapproximation error depends on the smoothness of the function $f$ and thesampling technique. For instance, Monte Carlo (MC) sampling yields aconvergence of the root mean square error (RMSE) of order $N^{-1/2}$ (where $N$is the number of samples) for functions $f$ with finite variance. RandomizedQMC (RQMC), a combination of MC and quasi-Monte Carlo (QMC), achieves a RMSE oforder $N^{-3/2+\varepsilon}$ under the stronger assumption that the integrandhas bounded variation. A combination of RQMC with local antithetic samplingachieves a convergence of the RMSE of order $N^{-3/2-1/s+\varepsilon}$ (where$s\ge1$ is the dimension) for functions with mixed partial derivatives up toorder two. Additional smoothness of the integrand does not improve the rate ofconvergence of these algorithms in general. On the other hand, it is known thatwithout additional smoothness of the integrand it is not possible to improvethe convergence rate. This paper introduces a new RQMC algorithm, for which weprove that it achieves a convergence of the root mean square error (RMSE) oforder $N^{-\alpha-1/2+\varepsilon}$ provided the integrand satisfies the strongassumption that it has square integrable partial mixed derivatives up to order$\alpha>1$ in each variable. Known lower bounds on the RMSE show that this rateof convergence cannot be improved in general for integrands with thissmoothness. We provide numerical examples for which the RMSE convergesapproximately with order $N^{-5/2}$ and $N^{-7/2}$, in accordance with thetheoretical upper bound.